package com.example.leetcode.trainingcamp.week4.Sunday;

/**
 * 对链表进行插入排序。
 *
 * <p>插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。 每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
 *
 * <p>
 *
 * <p>插入排序算法：
 *
 * <p>插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
 * 重复直到所有输入数据插入完为止。
 *
 * <p>示例 1：
 *
 * <p>输入: 4->2->1->3 输出: 1->2->3->4 示例 2：
 *
 * <p>输入: -1->5->3->4->0 输出: -1->0->3->4->5
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/insertion-sort-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test147 {

    ListNode newHead = new ListNode();
    ListNode tail = newHead;

    public ListNode insertionSortList(ListNode head) {
        ListNode p = head;
        while (p != null){
            ListNode next = p.next;
            add(p);
            p = next;
        }
        return newHead.next;
    }

    public void add (ListNode node){
        if (newHead.next == null){
            tail.next = node;
            tail = node;
            tail.next = null;
        }else {
            ListNode pre = newHead;
            while (true){
                if (pre.next != null && pre.next.val >= node.val){
                    node.next = pre.next;
                    pre.next = node;
                    break;
                }
                if (pre.next == null){
                    pre.next = node;
                    tail = node;
                    tail.next = null;
                    break;
                }
                pre = pre.next;
            }
        }
    }
}


class Demo147{
  public static void main(String[] args) {
    ListNode head = new ListNode(4);
    head.next = new ListNode(2);
    head.next.next = new ListNode(1);
    head.next.next.next = new ListNode(3);
  //  head.next.next.next.next = new ListNode(0);
    Test147 t = new Test147();
    ListNode listNode = t.insertionSortList(head);
    while (listNode!= null){
      System.out.println(listNode.val+" ");
      listNode = listNode.next;
    }
  }
}





class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val;this.next = next; }
}